public class code2 {

    // top101 二叉搜索树转换为一个排序双向链表

    public TreeNode Convert(TreeNode pRootOfTree) {
        // 可以直接定义出一个 list 顺序表对树进行中序遍历后存储起来
        ArrayList<TreeNode> list = new ArrayList<>();

        // 先来判断一下当前树为 null 的情况
        if (pRootOfTree == null) {
            return null;
        }

        // 实现一个方法现将各个元素存储到顺序表中
        putIn(list, pRootOfTree);

        // 这只是一个测试当前排序是否符合要求
        // for(int j = 0; j < list.size(); j++) {
        //     System.out.println(list.get(j).val);
        // }

        // 通过循环将所有的元素向右侧连接一遍
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).right = list.get(i + 1);
        }
        // 让最后一个位置的元素的 right 指向 null
        list.get(list.size() - 1).right = null;

        // 在通过一遍循环将元素在全部向左侧连接一遍
        for (int i = 1; i < list.size(); i++) {
            list.get(i).left = list.get(i - 1);
        }
        // 最后在将第一个元素指向null
        list.get(0).left = null;
        return list.get(0);
    }

    private static void putIn(ArrayList<TreeNode> list, TreeNode root) {
        // 进行中序遍历
        if (root == null) {
            return;
        }

        if(root.left != null) {
            putIn(list, root.left);
        }
        list.add(root);
        if(root.right != null) {
            putIn(list, root.right);
        }
    }
}
